package main

import "fmt"

/*
斐波那契数列：0,1,1,2,3,5,8...

	规律：从第三个数开始，每个数都是前两个数之和
	动态规划表达式：
		f(i): 表示 第i个数
	动态规划方程：
		f(i) = f(i-1)+f(i-2) ; i>=3
		f(0)=0
		f(1)=1
*/
func fibonacci1(n int) int {
	f := make([]int, n+1)
	f[0], f[1] = 0, 1
	for i := 2; i <= n; i++ {
		f[i] = f[i-1] + f[i-2] // 当前数据 = 前两项之和
	}
	return f[n]
}

/*
优化：

	上面的解法是标准的动态规划思路，从初始化逐个递推出后面的值
	时间复杂度：O(n)
	空间复杂度：O(n)

	实际上，推出后面一个数，只需要前面的两个数，倒数第三个数以前的空间都浪费掉了
	所以，只要一个能保存两个数的空间就足够了，空间复杂度降低至 O(1)
	思路：用一个长度为2的循环数组，每次替换掉倒数第三个数
*/
func fibonacci2(n int) int {
	f := [2]int{}
	f[0], f[1] = 0, 1
	for i := 2; i <= n; i++ {
		f[i&1] = f[0] + f[1] // 当前数据 = 前两项之和
	}
	return f[n&1]
}

func main() {
	n := 8
	fmt.Println(fibonacci1(n))
	fmt.Println(fibonacci2(n))
}
